//package work;
//
//import java.util.HashMap;
//import java.util.List;
//import java.util.Stack;
//
//public class UnionFindSet{
//    //key: 值 value: 带值节点
//    public HashMap<Integer, Node> valueMap;
//    //key: 子节点 value: 父节点
//    public HashMap<Node, Node> fatherMap;
//    //key: 头节点 value: 容量
//    public HashMap<Node,Integer> capacity;
//
//    public UnionFindSet(List<Integer> list){
//        valueMap = new HashMap<>();
//        fatherMap = new HashMap<>();
//        capacity = new HashMap<>();
//        for (Integer value : list) {
//            Node node = new Node(value);
//            valueMap.put(value,node);
//            fatherMap.put(node,node);
//            capacity.put(node,1);
//        }
//    }
//
//
//    public Node getHead(Node node){
//        Stack<Node> stack = new Stack<>();
//        while (fatherMap.get(node)!=node){
//            stack.push(node);
//            node = fatherMap.get(node);
//        }
//        while (!stack.isEmpty()){
//            Node pop = stack.pop();
//            fatherMap.put(pop,node);
//        }
//        return node;
//    }
//
//
//    public boolean isSameSet(Integer a,Integer b){
//        if(valueMap.containsKey(a)&&valueMap.containsKey(b)){
//            return getHead(valueMap.get(a))==getHead(valueMap.get(b));
//        }
//
//        return false;
//    }
//
//
//    public void union(Integer a,Integer b){
//        //合并
//        //1.先判断是不是存在
//        //2.存在，取得头节点，判断容量大小，big small大小节点
//        if(valueMap.containsKey(a)&&valueMap.containsKey(b)){
//            Node a1 = getHead(valueMap.get(a));
//            Node b1 = getHead(valueMap.get(b));
//            if(a1!=b1){
//                Node big = capacity.get(a1)>capacity.get(b1)?a1:b1;
//                Node small = capacity.get(a1)>capacity.get(b1)?b1:a1;
//                fatherMap.put(small,big);
//                capacity.put(big,capacity.get(big)+capacity.get(small));
//                capacity.remove(small);
//            }
//        }
//    }
//}
